package com.googlecode.lohr.parser.combinators.matcher;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

import com.googlecode.lohr.parser.combinators.MatchError;
import com.googlecode.lohr.parser.combinators.MatchResults;
import com.googlecode.lohr.parser.combinators.node.AbstractNode;

/**
 * A MatchContext is used to invoke parse text by invoking the doMatch method 
 * and passing a Matcher.
 * 
 * MatchContext manages the parsing process.
 * MatchContext implements strategies for memoizing match results 
 * and avoiding recursion.
 * 
 * Specificially, MatchContext avoids left recursion using the memoization 
 * techniques described in the paper "Memoization in Top-Down Parsing" by
 * Mark Johnson 
 *   
 * @author ted stockwell
 *
 */
public class MatchContext {
	private static final long serialVersionUID = 1L;
	private static String tabstring= "\t";
	private final String tabs() {
		if (tabstring.length() < _tabs) {
			tabstring= "";
			for (int i= _tabs*2; 0 < i--;)
				tabstring+= '\t';
		}
		return tabstring.substring(0, _tabs);
	}
	
	private class CacheEntry {
		
		private int position;
		private Matcher _matcher; 
		private ArrayList<AbstractNode> _matches;
		private MatchError _error;
		private HashSet<MatchListener> _listeners= new HashSet<MatchListener>();
		private boolean _isComplete= false;
		CacheEntry(Matcher matcher, int position) {
			this.position= position;
			_matcher= matcher;
		}
		synchronized public void addListener(MatchListener listener) {
			if (listener != null) {
				if (!_listeners.contains(listener)) {
					_listeners.add(listener);
					if (_matches != null) {
						for (AbstractNode node : new ArrayList<AbstractNode>(_matches)) {
							listener.onMatchFound(node);
						}
					}
					if (_isComplete) {
						listener.onMatchComplete(_error);
					}
				}
			}
		}
		synchronized public void addMatch(AbstractNode match) {
			if (_isComplete && !_continuing)
				throw new RuntimeException("this matcher has already been completed"); 
			if (_matches == null)
				_matches= new ArrayList<AbstractNode>();
			if (!_matches.contains(match)) {
				_matches.add(match);
				for (MatchListener listener:_listeners) {
					listener.onMatchFound(match);
				}
			}
		}
		public void addError(MatchError error) {
			// just save the error.
			// if no matches are found then the error will be send to listeners
			if (_error == null || error.position < _error.position)
				_error= error;
		}
		public void complete() {
			if (!_isComplete) {
				_isComplete= true;
				// send complete notification
				for (MatchListener listener:new HashSet<MatchListener>(_listeners)) {
					listener.onMatchComplete(_error);
				}
				if (_continuing)
					if (ChoiceMatcher.class.isAssignableFrom(_matcher.getClass())) 
						_isComplete= false;
				
//				if (_error == null)
//					if (_matches == null || _matches.isEmpty())
//						throw new RuntimeException("A match cannot be completed until either some matches or found or an error occurs");
			}
		}
		public boolean isComplete() { return _isComplete; }
	}
	
	
	
	private String _input;
	private HashMap<Matcher, Map<Integer, CacheEntry>> _cache= 
		new HashMap<Matcher, Map<Integer,CacheEntry>>();
	
	private boolean _trace= true;
	private int _tabs= 0;
	private HashMap<Matcher, Boolean> _traceFlags= new HashMap<Matcher, Boolean>();
	private ArrayList<CacheEntry> _matchCallStack= new ArrayList<CacheEntry>();
	private boolean _inProgress= false;
	private boolean _continuing= false;
	private ArrayList<MatchCall> _callStack= new ArrayList<MatchCall>();
	
	private static class MatchCall {
		Matcher matcher;
		int start;
		MatchListener listener;
		public MatchCall(Matcher matcher, int start, MatchListener listener) {
			this.matcher= matcher;
			this.start= start;
			this.listener= listener;
		}
	}
	
	
	/**
	 * A convenience method for performing a single match.
	 */
	public static MatchResults match(Matcher matcher, String input) {
		return new MatchContext(input).getMatchResults(matcher, 0);
	}
	
	public MatchContext(String input) {
		_input= input;
	}
	
	
	/**
	 * This method is used to perform matches.
	 */
	public void doMatch(Matcher matcher, int start, MatchListener listener) {
		_callStack.add(new MatchCall(matcher, start, listener));

		if (_inProgress) 
			return;
		_inProgress= true;

		while (!_callStack.isEmpty()) {
			MatchCall call= _callStack.remove(0);

			// setup trace 
			boolean otrace= _trace;
			Boolean traceFlag= _traceFlags.get(call.matcher);
			if (traceFlag != null) 
				_trace= traceFlag.booleanValue();
			boolean trace= _trace;
			if (trace) _tabs++;
			if (trace) System.out.println(tabs()+"doMatch("+call.matcher.getLabel()+","+call.start+")");		
			try {

				// return any cached results
				CacheEntry entry= getCachedResults(call.matcher, call.start);
				if (entry != null) {
					if (trace)System.out.println(tabs()+"match entry already exists, adding listener");		
					entry.addListener(call.listener);
					continue;
				}

				// create cache entry
				entry= createCacheEntry(call.matcher, call.start);
				entry.addListener(call.listener);

				// evaluate matcher 
				call.matcher.match(this, call.start);

				//matchComplete(matcher, start);
			} 
			finally {
				if (trace) {
					System.out.println(tabs()+"/doMatch");		
					_tabs--;
				}
				_trace= otrace;
			}
		}
		
		_inProgress=false;
	}
	

	public String getInput() {
		return _input;
	}

	public CacheEntry getCachedResults(Matcher matcher, int start) {
		CacheEntry entry= null;
		Map<Integer,CacheEntry> entries= _cache.get(matcher);
		if (entries != null)
			entry= entries.get(start);
		return entry;
	}
	
	protected CacheEntry createCacheEntry(Matcher matcher, int start) {
		Map<Integer,CacheEntry> results= _cache.get(matcher);
		if (results == null) {
			results= new HashMap<Integer, CacheEntry>();
			_cache.put(matcher, results);
		}
		CacheEntry entry= results.get(start);
		if (entry == null) {
			entry= new CacheEntry(matcher, start);
			results.put(start, entry);
			_matchCallStack.add(entry);
		}
		return entry;
	}
	
	public void trace(Matcher matcher, boolean trace) {
		_traceFlags.put(matcher, trace ? Boolean.TRUE : Boolean.FALSE);
	}


	public void matchFound(Matcher matcher, int start, AbstractNode match) {
		if (_trace)System.out.println(tabs()+"match found:"+matcher.getLabel()+","+start+", match="+match.toString());		
		CacheEntry entry= getCachedResults(matcher, start);
		assert entry != null;
		entry.addMatch(match);
	}


	public void matchComplete(Matcher matcher, int start) {
		matchComplete(matcher, start, null);
	}

	public void matchComplete(Matcher matcher, int start, MatchError error) {
		CacheEntry entry= getCachedResults(matcher, start);
		if (!entry.isComplete()) {
			_matchCallStack.remove(entry); 
			if (_trace){
				System.out.print(tabs()+"match completed:"+matcher.getLabel()+","+start);
				if (error != null) 
					System.out.print(",error:"+error);
				System.out.println();
			}
			assert entry != null;
			if (error != null)
				entry.addError(error);
			entry.complete();
		}
	}


	public void matchError(Matcher matcher, int start, MatchError error) {
		if (_trace)System.out.println(tabs()+"match error:"+matcher.getLabel()+","+start);		
		CacheEntry entry= getCachedResults(matcher, start);
		assert entry != null;
		entry.addError(error);
	}
	
	/**
	 * A convenience method for performing a single match.
	 * This method should only be used for Matchers that are terminals, since they 
	 * are guaranteed to complete during the call to doMatch.
	 * Maybe non-terminals also complete during a call to doMatch but I do not 
	 * know that for sure.  
	 */
	public MatchResults getMatchResults(Matcher matcher, int start) {
		
		doMatch(matcher, start, null);

		// complete all matchers
		while (!_matchCallStack.isEmpty() && matcher == _matchCallStack.get(0)._matcher) {
			boolean continued= false;
			for (int i= _matchCallStack.size(); 0 < i--;) {
				CacheEntry entry= _matchCallStack.get(i);
				if (entry._matcher.getClass().isAssignableFrom(ChoiceMatcher.class)) {
					continued= true;
					_matchCallStack.remove(entry);
					if (_trace){
						System.out.print(tabs()+"match continue:"+entry._matcher.getLabel()+","+start);
						System.out.println();
					}
					_continuing= true;
					entry.complete();
					_continuing= false;
					entry._isComplete= false;
					break;
				}
			}
			if (!continued)
				break;
//			if (entry._error != null || (entry._matches != null && !entry._matches.isEmpty())) {			
//				matchComplete(entry._matcher, entry.position);
//			}
//			else {
//				matchError(entry._matcher, entry.position, new MatchError("No matches found", entry.position));
//			}
		}
		
		CacheEntry entry= getCachedResults(matcher, start);
		assert entry.isComplete();
		if ((entry._matches == null || entry._matches.isEmpty()) && entry._error != null)
			return new MatchResults(entry._error);
		if (entry._matches == null)
			return new MatchResults(Collections.<AbstractNode>emptyList()); 
		return new MatchResults(entry._matches); 
	}

	public boolean hasMatches(Matcher matcher, int start) {
		CacheEntry entry= getCachedResults(matcher, start);
		assert entry != null;
		return entry._matches != null && !entry._matches.isEmpty();  
	}

	public boolean isComplete(Matcher matcher, int start) {
		CacheEntry entry= getCachedResults(matcher, start);
		assert entry != null;
		return entry.isComplete();  
	}

	public MatchError getMatchError(Matcher matcher, int start) {
		CacheEntry entry= getCachedResults(matcher, start);
		if (entry == null)
			return null;
		return entry._error;  
	}
	
}
